{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Turbulent Subarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxTurbulenceSize"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长湍流子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组 <code>arr</code>&nbsp;，返回 <code>arr</code>&nbsp;的&nbsp;<em>最大湍流子数组的<strong>长度</strong></em><strong>&nbsp;</strong>。</p>\n",
    "\n",
    "<p>如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是&nbsp;<strong>湍流子数组</strong>&nbsp;。</p>\n",
    "\n",
    "<p>更正式地来说，当 <code>arr</code>&nbsp;的子数组&nbsp;<code>A[i], A[i+1], ..., A[j]</code>&nbsp;满足仅满足下列条件时，我们称其为<em>湍流子数组</em>：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>若&nbsp;<code>i &lt;= k &lt; j</code>&nbsp;：\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>当 <code>k</code>&nbsp;为奇数时，&nbsp;<code>A[k] &gt; A[k+1]</code>，且</li>\n",
    "\t\t<li>当 <code>k</code> 为偶数时，<code>A[k] &lt; A[k+1]</code>；</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li><strong>或 </strong>若&nbsp;<code>i &lt;= k &lt; j</code>&nbsp;：\n",
    "\t<ul>\n",
    "\t\t<li>当 <code>k</code> 为偶数时，<code>A[k] &gt; A[k+1]</code>&nbsp;，且</li>\n",
    "\t\t<li>当 <code>k</code>&nbsp;为奇数时，&nbsp;<code>A[k] &lt; A[k+1]</code>。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [9,4,2,10,7,8,8,1,9]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>arr[1] &gt; arr[2] &lt; arr[3] &gt; arr[4] &lt; arr[5]</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [4,8,12,16]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [100]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 4 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= arr[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-turbulent-subarray](https://leetcode.cn/problems/longest-turbulent-subarray/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-turbulent-subarray](https://leetcode.cn/problems/longest-turbulent-subarray/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[9,4,2,10,7,8,8,1,9]', '[4,8,12,16]', '[100]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        left,right=0,0\n",
    "        res=1\n",
    "        while right<len(arr)-1:\n",
    "            if left==right:\n",
    "                if arr[left]==arr[left+1]:\n",
    "                    left+=1\n",
    "                right+=1\n",
    "            else:\n",
    "                if arr[right-1]<arr[right] and arr[right]>arr[right+1]:\n",
    "                    right+=1\n",
    "                elif arr[right-1]>arr[right] and arr[right]<arr[right+1]:\n",
    "                    right+=1\n",
    "                else:\n",
    "                    left=right\n",
    "            res=max(res,right-left+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, A: List[int]) -> int:\n",
    "        le = len(A)\n",
    "        if len(set(A))==1: return 1\n",
    "        dp = [1]*le\n",
    "        res = 1\n",
    "\n",
    "        for i in range(1, le-1):\n",
    "            if (A[i]>A[i-1] and A[i]>A[i+1]) or (A[i]<A[i-1] and A[i]<A[i+1]):\n",
    "                dp[i] = dp[i-1]+1\n",
    "\n",
    "        return max(dp)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = 0\n",
    "        n = len(arr)\n",
    "        ret = 1\n",
    "        while right < n - 1:\n",
    "            if left == right:\n",
    "                if arr[left] == arr[left+1]:left += 1\n",
    "                right += 1\n",
    "            else:\n",
    "                if arr[right - 1] < arr[right] and arr[right] > arr[right + 1]:right += 1\n",
    "                elif arr[right - 1] > arr[right] and arr[right] < arr[right + 1]:right += 1\n",
    "                #无法构成湍流子数组\n",
    "                else: left = right\n",
    "            ret = max(ret,right - left + 1)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "0表示上升, arr[i-1] < arr[i]\n",
    "1表示下降, arr[i-1] > arr[i]\n",
    "当 arr[i-1] < arr[i], 那么必须满足 arr[i-2] > arr[i-1]\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        ans = 1\n",
    "        f = [1, 1]\n",
    "        n = len(arr)\n",
    "        for i in range(1, n):\n",
    "            a, b = f[0], f[1]\n",
    "            f[0] = b + 1 if arr[i] > arr[i-1] else 1\n",
    "            f[1] = a + 1 if arr[i] < arr[i-1] else 1\n",
    "            ans = max(ans, max(f))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "0(up)表示上升, arr[i-1] < arr[i]\n",
    "1(down)表示下降, arr[i-1] > arr[i]\n",
    "当 arr[i-1] < arr[i], 那么必须满足 arr[i-2] > arr[i-1]\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        ans = 1\n",
    "        up, down = 1, 1\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i-1] < arr[i]:\n",
    "                up, down = down + 1, 1\n",
    "            elif arr[i-1] > arr[i]:\n",
    "                up, down = 1, up + 1\n",
    "            else:\n",
    "                up, down = 1, 1\n",
    "            ans = max(ans, max(up, down))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        n, c1, c2, ans = len(arr), 1, 1, 1\n",
    "        for i in range(1, n):\n",
    "            if arr[i] > arr[i - 1]:\n",
    "                tmp1, tmp2 = c2 + 1, 1\n",
    "                c1, c2 = tmp1, tmp2\n",
    "            elif arr[i] < arr[i - 1]:\n",
    "                tmp1, tmp2 = 1, c1 + 1\n",
    "                c1, c2 = tmp1, tmp2\n",
    "            else:\n",
    "                c1, c2 = 1, 1\n",
    "            ans = max([ans, c1, c2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        ans = 1\n",
    "        up_prev = down_prev = 1\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i-1]>arr[i]:\n",
    "                down_prev = up_prev+1\n",
    "                up_prev = 1\n",
    "                ans = max(down_prev, ans)\n",
    "            elif arr[i-1]<arr[i]:\n",
    "                up_prev = down_prev+1\n",
    "                down_prev = 1\n",
    "                ans = max(up_prev, ans)\n",
    "            else:\n",
    "                down_prev = 1\n",
    "                up_prev = 1\n",
    "            \n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        down, up = 1, 1\n",
    "        res = 1\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i-1] > arr[i]:\n",
    "                down = up + 1\n",
    "                up = 1\n",
    "            elif arr[i-1] < arr[i]:\n",
    "                up = down + 1\n",
    "                down = 1\n",
    "            else:\n",
    "                down, up = 1, 1\n",
    "            res = max(res, down, up)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        left, right = 0, 1\n",
    "        ans = 1\n",
    "        while right < len(arr):\n",
    "            if arr[right] == arr[right-1]: left = right\n",
    "            elif right != 1 and arr[right] > arr[right-1] and arr[right-1] > arr[right-2]: left = right -1\n",
    "            elif right != 1 and arr[right] < arr[right-1] and arr[right-1] < arr[right-2]: left = right -1\n",
    "            ans = max(ans, right-left+1)\n",
    "            right += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        if len(arr) == 1:\n",
    "            return 1\n",
    "        greater = 1\n",
    "        less = 1\n",
    "        max_v = 1\n",
    "        for k in range(1,len(arr)):\n",
    "            if arr[k] > arr[k-1]:\n",
    "                greater = less + 1\n",
    "                less = 1\n",
    "                max_v = max(max_v,greater )\n",
    "            elif arr[k] < arr[k-1]:\n",
    "                less = greater + 1\n",
    "                greater = 1\n",
    "                max_v = max(max_v,less)\n",
    "            else:\n",
    "                less = 1\n",
    "                greater = 1\n",
    "        return max_v\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        if not arr: return 0\n",
    "        if len(arr) == 1: return 1\n",
    "\n",
    "        L, R = 0, 1 # pointers keeping track of the current window\n",
    "        result = 0\n",
    "        prev = \"\"\n",
    "\n",
    "        while R < len(arr): # scan the array with the R pointer\n",
    "            if arr[R-1] > arr[R] and prev != \">\":\n",
    "                prev = \">\"\n",
    "                # good case\n",
    "                result = max(result, R - L)\n",
    "                R += 1\n",
    "                            \n",
    "            elif arr[R-1] < arr[R] and prev != \"<\":\n",
    "                prev = \"<\"\n",
    "                # goode case\n",
    "                result = max(result, R - L)\n",
    "                R += 1\n",
    "                \n",
    "            else:\n",
    "                # bad case, start over again\n",
    "                prev = \"\"\n",
    "                if arr[R-1] == arr[R]:\n",
    "                    R += 1\n",
    "                L = R - 1\n",
    "                \n",
    "\n",
    "        return result + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        if len(arr) == 1:return 1\n",
    "        l = 0\n",
    "        r = 1\n",
    "        n = len(arr)\n",
    "        res = -1\n",
    "      \n",
    "        while r < n :\n",
    "          \n",
    "            if r < n - 1 and (arr[r] - arr[r - 1]) * (arr[r] -arr[r + 1]) > 0 : \n",
    "                r += 1\n",
    "            else:\n",
    "                if arr[r] == arr[r - 1]:\n",
    "                    res = max(res , r - l ) \n",
    "                else:\n",
    "                    res = max(res , r - l + 1)\n",
    "                l = r\n",
    "                r += 1\n",
    "        return res \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        asize = len(arr)\n",
    "        # down_init = [1]*asize\n",
    "        # up_init = [1]*asize\n",
    "\n",
    "        ans = 1\n",
    "        up_prev = down_prev = 1\n",
    "        for i in range(1, asize):\n",
    "            if arr[i-1]>arr[i]:\n",
    "                down_prev = up_prev+1\n",
    "                up_prev = 1\n",
    "            elif arr[i-1]<arr[i]:\n",
    "                up_prev = down_prev+1\n",
    "                down_prev = 1\n",
    "            else:\n",
    "                down_prev = 1\n",
    "                up_prev = 1\n",
    "            \n",
    "            ans = max([down_prev, up_prev, ans])\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        h,t=0,0\n",
    "        ans=1\n",
    "        temp=1\n",
    "        flag=0\n",
    "        while t<len(arr)-1:\n",
    "            if arr[t+1]>arr[t] and flag!=-1:\n",
    "                temp+=1\n",
    "                flag=-1\n",
    "                t=t+1\n",
    "            elif arr[t+1]<arr[t] and flag!=1:\n",
    "                temp+=1\n",
    "                flag=1\n",
    "                t=t+1\n",
    "            else:\n",
    "                flag=0\n",
    "                temp=1\n",
    "                if arr[t+1]==arr[t]: t+=1\n",
    "            ans=max(ans,temp)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "\n",
    "        dp = [0] * (len(arr) + 1)\n",
    "        dp[1] = 1\n",
    "        if len(arr) >= 2 and arr[0] != arr[1]:\n",
    "            dp[2] = 2\n",
    "\n",
    "        for i in range(3, len(dp)):\n",
    "            if arr[i-2] > arr[i-3]:\n",
    "                if arr[i-1] > arr[i-2]:\n",
    "                    dp[i] = 2\n",
    "                elif arr[i-1] < arr[i-2]:\n",
    "                    dp[i] = dp[i-1] + 1 \n",
    "                else:\n",
    "                    dp[i] = 2\n",
    "            elif arr[i-2] < arr[i-3]:\n",
    "                if arr[i-1] > arr[i-2]:\n",
    "                    dp[i] = dp[i-1] + 1 \n",
    "                elif arr[i-1] < arr[i-2]:\n",
    "                    dp[i] = 2\n",
    "                else:\n",
    "                    dp[i] = 2\n",
    "            else:\n",
    "                if arr[i-1] > arr[i-2]:\n",
    "                    dp[i] = 2\n",
    "                elif arr[i-1] < arr[i-2]:\n",
    "                    dp[i] = 2\n",
    "                else:\n",
    "                    dp[i] = 1\n",
    "\n",
    "        \n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        if len(arr)<=1:\n",
    "            return len(arr)\n",
    "        if len(arr) == 2 and arr[0]!=arr[1]:\n",
    "            return 2\n",
    "        count = 0\n",
    "        left = 0\n",
    "        last_big = arr[0]>arr[1]\n",
    "        for i in range(1, len(arr)):\n",
    "            if i-left<=1 :\n",
    "                if arr[i-1]!=arr[i]:\n",
    "                    last_big = arr[i-1]>arr[i]\n",
    "                else:\n",
    "                    left = i\n",
    "            else:\n",
    "                if arr[i-1]>arr[i]:\n",
    "                    if last_big:\n",
    "                        left = i-1\n",
    "                    else:\n",
    "                        last_big = not last_big\n",
    "                elif arr[i-1]<arr[i]:\n",
    "                    if last_big:\n",
    "                        last_big = not last_big\n",
    "                    else:\n",
    "                        left = i-1\n",
    "                else:\n",
    "                    left = i\n",
    "            count = max(count, i-left+1)\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        up = down = res = 0\n",
    "        for i in range(1, len(arr)):\n",
    "            if i % 2:\n",
    "                if arr[i] > arr[i-1]:\n",
    "                    up += 1\n",
    "                    down =0\n",
    "                elif arr[i] == arr[i-1]:\n",
    "                    up = down =0\n",
    "                else:\n",
    "                    down += 1\n",
    "                    up = 0\n",
    "            else:\n",
    "                if arr[i] < arr[i-1]:\n",
    "                    up += 1\n",
    "                    down =0\n",
    "                elif arr[i] == arr[i-1]:\n",
    "                    up = down =0\n",
    "                else:\n",
    "                    down += 1\n",
    "                    up = 0\n",
    "            res = max(res, down, up)\n",
    "        return res + 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        if len(arr)<=1:\n",
    "            return len(arr)\n",
    "        if len(arr) == 2 and arr[0]!=arr[1]:\n",
    "            return 2\n",
    "        count = 0\n",
    "        left = 0\n",
    "        last_big = arr[0]>arr[1]\n",
    "        for i in range(1, len(arr)):\n",
    "            if i-left<=1:\n",
    "                if arr[i-1]!=arr[i]:\n",
    "                    last_big = arr[i-1]>arr[i]\n",
    "                else:\n",
    "                    left = i\n",
    "            else:\n",
    "                if arr[i-1]>arr[i]:\n",
    "                    if last_big:\n",
    "                        left = i-1\n",
    "                    else:\n",
    "                        last_big = not last_big\n",
    "                elif arr[i-1]<arr[i]:\n",
    "                    if last_big:\n",
    "                        last_big = not last_big\n",
    "                    else:\n",
    "                        left = i-1\n",
    "                else:\n",
    "                    left = i\n",
    "            count = max(count, i-left+1)\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        # 一升一降\n",
    "        n = len(arr)\n",
    "        if n==1:\n",
    "            return 1\n",
    "        left = 0\n",
    "        right = 1\n",
    "        max_len = 1\n",
    "        while right<n:\n",
    "            t = 0\n",
    "            if arr[right]-arr[left]>0:\n",
    "                t = -1\n",
    "            elif arr[right]-arr[left]<0:\n",
    "                t = 1\n",
    "\n",
    "            while right<n and (arr[min(right+1, n-1)]-arr[right])*t>0 and t!=0:\n",
    "                t *= -1\n",
    "                right+=1\n",
    "            if right-left+1>max_len and t!=0:\n",
    "                    print(left, right)\n",
    "                    max_len = right-left+1\n",
    "            if t==0:\n",
    "                left += 1\n",
    "            else:\n",
    "                left = right\n",
    "            right=left+1\n",
    "            \n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        width, N = 1, len(arr)\n",
    "        L, R = 0, 1\n",
    "        \n",
    "        while R < N:\n",
    "            if arr[L] > arr[R]:\n",
    "                sign = - 1\n",
    "                while R < N-1 and sign*(arr[R+1] - arr[R]) < 0:\n",
    "                    R += 1\n",
    "                    sign *= -1\n",
    "                width = max(R-L+1, width)\n",
    "            \n",
    "            elif arr[L] < arr[R]:\n",
    "                sign = -1\n",
    "                while R <N-1 and sign*(arr[R]-arr[R+1]) < 0:\n",
    "                    R +=1\n",
    "                    sign *= -1\n",
    "                width = max(width, R-L+1)\n",
    "            else:\n",
    "                pass\n",
    "            \n",
    "            L=R\n",
    "            R+=1\n",
    "        return width\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        up=[1]*n\n",
    "        down=[1]*n\n",
    "        #res=1\n",
    "        for i in range(1,n):\n",
    "            if arr[i-1]<arr[i]:\n",
    "                up[i]=down[i-1]+1\n",
    "            elif arr[i-1]>arr[i]:\n",
    "                down[i]=up[i-1]+1\n",
    "            #res=max(res,max(up[i],down[i]))\n",
    "        return max(max(up),max(down))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        asize = len(arr)\n",
    "        down_init = [1]*asize\n",
    "        up_init = [1]*asize\n",
    "\n",
    "        ans = 1\n",
    "        for i in range(1, asize):\n",
    "            if arr[i-1]>arr[i]:\n",
    "                down_init[i] = up_init[i-1]+1\n",
    "            elif arr[i-1]<arr[i]:\n",
    "                up_init[i] = down_init[i-1]+1\n",
    "            \n",
    "            ans = max([down_init[i], up_init[i], ans])\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        if len(arr)==1:return 1\n",
    "        if arr[1]==arr[0]:\n",
    "            ans=cur=1\n",
    "        else:\n",
    "            ans=cur=2\n",
    "        \n",
    "        n=len(arr)\n",
    "        \n",
    "        for i in range(2,n):\n",
    "            if (arr[i]-arr[i-1])*(arr[i-1]-arr[i-2])<0:\n",
    "                cur+=1\n",
    "            else:\n",
    "                cur=1+(arr[i]!=arr[i-1])\n",
    "        \n",
    "            ans=max(ans,cur)\n",
    "            \n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        up=[1]*n\n",
    "        down=[1]*n\n",
    "        for i in range(1,n):\n",
    "            if arr[i]<arr[i-1]:\n",
    "                down[i]=up[i-1]+1\n",
    "            elif arr[i]>arr[i-1]:\n",
    "                up[i]=down[i-1]+1\n",
    "        # print(up,down)\n",
    "        return max(max(up),max(down))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        n = len(arr)\n",
    "        up = [1] * n\n",
    "        dn = [1] * n\n",
    "        for i in range(1, n):\n",
    "            if arr[i-1] < arr[i]:\n",
    "                up[i] = dn[i-1] + 1\n",
    "            elif arr[i-1] > arr[i]:\n",
    "                dn[i] = up[i-1] + 1\n",
    "        return max(max(up), max(dn))\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        #快慢双指针\n",
    "        ans = 1\n",
    "        size = len(arr)\n",
    "        slow, fast =0, 1\n",
    "        while fast < size:\n",
    "            if arr[fast] == arr[fast - 1]:\n",
    "                slow = fast\n",
    "            elif fast != 1 and arr[fast - 2] < arr[fast - 1] and arr[fast - 1] < arr[fast]:\n",
    "                slow = fast - 1\n",
    "            elif fast != 1 and arr[fast - 2] > arr[fast - 1] and arr[fast - 1] > arr[fast]:\n",
    "                slow = fast - 1\n",
    "            \n",
    "            ans = max(ans, fast - slow + 1)\n",
    "            print(fast, ans)\n",
    "            fast += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [1] * n\n",
    "        # dp[i]: longest turbulent subarray ends with arr[i]\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            if i == 1 and arr[i] != arr[i-1]:\n",
    "                dp[i] = dp[i-1]+1\n",
    "                continue\n",
    "            if (arr[i]>arr[i-1] and arr[i-1]<arr[i-2]) or (arr[i]<arr[i-1] and arr[i-1]>arr[i-2]):\n",
    "                dp[i] = dp[i-1]+1\n",
    "            elif arr[i] != arr[i-1]:\n",
    "                dp[i] += 1\n",
    "\n",
    "        print(dp)\n",
    "        return max(dp)\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        if n <= 1: return n\n",
    "        res = 1\n",
    "        up = [1 for _ in range(n)]\n",
    "        down = [1 for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            if arr[i] > arr[i-1]:\n",
    "                up[i] = down[i-1] + 1\n",
    "                res = max(res, up[i])\n",
    "            elif arr[i] < arr[i-1]:\n",
    "                down[i] = up[i-1] + 1\n",
    "                res = max(res, down[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        if len(arr) == 1:\n",
    "            return 1\n",
    "        res = []\n",
    "        for a, b in pairwise(arr):\n",
    "            if a < b:\n",
    "                res.append(-1)\n",
    "            elif a > b:\n",
    "                res.append(1)\n",
    "            else:\n",
    "                res.append(0)\n",
    "        n = len(res)\n",
    "        dp = [1] * n \n",
    "        if res[0] == 0:\n",
    "            dp[0] = 0\n",
    "        for i in range(1, n):\n",
    "            if res[i] == 0:\n",
    "                dp[i] = 0\n",
    "            elif res[i] * res[i - 1] == -1:\n",
    "                dp[i] = dp[i - 1] + 1\n",
    "        return max(dp) + 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        symbol = [[]]\n",
    "        for i, j in zip(arr[1:], arr[:-1]):\n",
    "            if j > i:\n",
    "                symbol[-1].append(1)\n",
    "            elif j < i:\n",
    "                symbol[-1].append(-1)\n",
    "            elif j == i:\n",
    "                symbol.append([])\n",
    "        # print(symbol)\n",
    "        res = 1\n",
    "        for item in symbol:\n",
    "            if item:\n",
    "                res = max(res, self.get_length(item))\n",
    "        return res\n",
    "\n",
    "    def get_length(self, symbol):\n",
    "        cnt = 1\n",
    "        left = 0\n",
    "        # print(symbol)\n",
    "        for right in range(1, len(symbol)):\n",
    "            if symbol[right] * symbol[right - 1] != -1:\n",
    "                left = right\n",
    "            \n",
    "            cnt = max(cnt, right - left + 1)\n",
    "            # print(cnt, left, right, symbol[left: right + 1])\n",
    "\n",
    "        return cnt + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        sign_list = []\n",
    "        for i in range(len(arr)-1):\n",
    "            if arr[i+1] < arr[i]:\n",
    "                sign_list.append(1)\n",
    "            elif arr[i+1] > arr[i]:\n",
    "                sign_list.append(-1)\n",
    "            else:\n",
    "                sign_list.append(0)\n",
    "        longest = 1\n",
    "        consecutive = False\n",
    "        length = 1\n",
    "        if len(sign_list) > 1:\n",
    "            for i in range(len(sign_list)-1):\n",
    "                if sign_list[i+1] * sign_list[i] < 0:\n",
    "                    consecutive = True\n",
    "                    length += 1\n",
    "                    final_len = length + 1\n",
    "                    if final_len > longest:\n",
    "                        longest = final_len\n",
    "                elif sign_list[i+1] * sign_list[i] > 0:\n",
    "                    final_len = length + 1\n",
    "                    if final_len > longest:\n",
    "                        longest = final_len\n",
    "                    consecutive = False\n",
    "                    length = 1\n",
    "                else:\n",
    "                    if consecutive:\n",
    "                        final_len = length + 1\n",
    "                        if final_len > longest:\n",
    "                            longest = final_len\n",
    "                        consecutive = False\n",
    "                        length = 1\n",
    "                    else:\n",
    "                        if sign_list[i] == sign_list[i+1]:\n",
    "                            length = 1\n",
    "                        else:\n",
    "                            final_len = length + 1\n",
    "                            if final_len > longest:\n",
    "                                longest = final_len\n",
    "        elif len(sign_list) == 1 and sign_list[0] != 0:\n",
    "            longest = 2\n",
    "        else:\n",
    "            longest = 1\n",
    "        return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        if n==1:\n",
    "            return(1)\n",
    "        elif n == 2:\n",
    "            if arr[0]!=arr[1]:\n",
    "                return(2)\n",
    "            else:\n",
    "                return(1)\n",
    "\n",
    "        dp1 = [1]*n # 0 < 1 > 2 < 3 \n",
    "        dp2 = [1]*n # 0 > 1 < 2 > 3 \n",
    "\n",
    "        i = 1\n",
    "        if arr[i]>arr[i-1]:\n",
    "            dp1[i] = 2\n",
    "        elif arr[i]<arr[i-1]:\n",
    "            dp2[i] = 2\n",
    "\n",
    "        for i in range(2,n):\n",
    "            print(i, i%2)\n",
    "            if i%2 == 0:\n",
    "                if arr[i]<arr[i-1]:\n",
    "                    dp1[i] = dp1[i-1]+1\n",
    "                elif arr[i]>arr[i-1]:\n",
    "                    dp2[i] = dp2[i-1]+1\n",
    "            else:\n",
    "                if arr[i]>arr[i-1]:\n",
    "                    dp1[i] = dp1[i-1]+1\n",
    "                elif arr[i]<arr[i-1]:\n",
    "                    dp2[i] = dp2[i-1]+1\n",
    "        # print(dp1)\n",
    "        # print(dp2)\n",
    "        return(max([max(dp1),max(dp2)]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, nums: List[int]) -> int:\n",
    "        # 动态规划\n",
    "        # 子问题定义：已nums[i]结尾的最长湍流子数组的长度\n",
    "        # 子问题联系：状态转移方程\n",
    "\n",
    "        # 存放长度\n",
    "        length = len(nums)\n",
    "        dp = [1 for _ in range(length)]\n",
    "\n",
    "        # 存放状态（0：小，1：大, 2：未知）\n",
    "        do = [2 for _ in range(length)]\n",
    "\n",
    "        # 连续子数组，O(n)时间复杂度\n",
    "        for i in range(1, length):\n",
    "            if do[i-1]==0:\n",
    "                if nums[i]>nums[i-1]:\n",
    "                    # 应该大\n",
    "                    dp[i] = dp[i-1]+1\n",
    "                    do[i] = 1\n",
    "                elif nums[i]==nums[i-1]:\n",
    "                    # 只有相等才可为2\n",
    "                    dp[i] = 1\n",
    "                    do[i] = 2\n",
    "                else:\n",
    "                    do[i] = 0\n",
    "                    dp[i] = 2\n",
    "            elif do[i-1]==1:\n",
    "                if nums[i]<nums[i-1]:\n",
    "                    # 应该小\n",
    "                    dp[i] = dp[i-1]+1\n",
    "                    do[i] = 0\n",
    "                elif nums[i]==nums[i-1]:\n",
    "                    # 只有相等才可为2\n",
    "                    dp[i] = 1\n",
    "                    do[i] = 2\n",
    "                else:\n",
    "                    dp[i] = 2\n",
    "                    do[i] = 1\n",
    "            else:\n",
    "                # 当前未知，则需要观察下一个元素\n",
    "                if nums[i]<nums[i-1]:\n",
    "                    dp[i] = dp[i-1]+1\n",
    "                    do[i] = 0\n",
    "                elif nums[i]>nums[i-1]:\n",
    "                    dp[i] = dp[i-1]+1\n",
    "                    do[i] = 1\n",
    "                else:\n",
    "                    # 继续未知\n",
    "                    dp[i] = 1\n",
    "                    do[i] = 2\n",
    "\n",
    "        print('dp = ', dp)\n",
    "        print('do = ', do)\n",
    "        return max(dp)\n",
    "\n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 最长摆动子串，类似的lc376求的是最长摆动子序列\n",
    "    def maxTurbulenceSize(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # dp[i][0] 表示以nums[i]结尾(选定)且最后一组元素是上升趋势的最长摆动子串的长度\n",
    "        # dp[i][1] 表示以nums[i]结尾(选定)且最后一组元素是下降趋势的最长摆动子串的长度\n",
    "        dp = [[1] * 2 for _ in range(n)] \n",
    "        res = 1\n",
    "        for i in range(1, n):\n",
    "            if nums[i] > nums[i-1]: # 最后一组元素是上升趋势\n",
    "                dp[i][0] = 1 + dp[i-1][1]\n",
    "                dp[i][1] = 1\n",
    "            elif nums[i] < nums[i-1]:\n",
    "                dp[i][0] = 1\n",
    "                dp[i][1] = 1 + dp[i-1][0]\n",
    "            else:\n",
    "                dp[i][0] = 1\n",
    "                dp[i][1] = 1\n",
    "            res = max(res, dp[i][0], dp[i][1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp1 = [0] * n  # <\n",
    "        dp2 = [0] * n  # >\n",
    "        for i in range(1,n):\n",
    "            if arr[i] > arr[i-1]:\n",
    "                dp2[i] = dp1[i-1] + 1\n",
    "            if arr[i] < arr[i-1]:\n",
    "                dp1[i] = dp2[i-1] + 1\n",
    "        return max(dp1+dp2)+1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        N = len(arr)\n",
    "        up = [1] * N\n",
    "        down = [1] * N\n",
    "        # res = 1\n",
    "        for i in range(1, N):\n",
    "            if arr[i - 1] < arr[i]:\n",
    "                up[i] = down[i - 1] + 1\n",
    "            elif arr[i - 1] > arr[i]:\n",
    "                down[i] = up[i - 1] + 1\n",
    "        return max(up+down)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        # ## 双指针\n",
    "        # pre = False\n",
    "        # left, right = 0, 1\n",
    "        # ans = 1\n",
    "        # while right < len(arr):\n",
    "        #     cur = (arr[right] - arr[right-1]) > 0\n",
    "        #     if cur == pre:\n",
    "        #         left = right - 1\n",
    "        #     if arr[right] == arr[right-1]:\n",
    "        #         left = right\n",
    "        #     right += 1\n",
    "        #     ans = max(ans, right-left)\n",
    "        #     pre = cur\n",
    "        # return ans\n",
    "\n",
    "        ## 动态规划\n",
    "        increase, decrease = [1], [1]\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i] > arr[i-1]:\n",
    "                increase.append(decrease[-1]+1)\n",
    "                decrease.append(1)\n",
    "            elif arr[i] < arr[i-1]:\n",
    "                decrease.append(increase[-1]+1)\n",
    "                increase.append(1)\n",
    "            else:\n",
    "                increase.append(1)\n",
    "                decrease.append(1)\n",
    "        return max(max(increase), max(decrease))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        n =len(arr)\n",
    "        dp = [(0,0) for i in range(n)]\n",
    "        ans= 1\n",
    "        if n<2:\n",
    "            return n\n",
    "        if arr[0] < arr[1]:\n",
    "            dp[1] = (1,2)\n",
    "            ans = 2\n",
    "        if arr[0] > arr[1]:\n",
    "            dp[1] = (-1,2)\n",
    "            ans=2\n",
    "        for i in range(2,n):\n",
    "            if arr[i] > arr[i-1]:\n",
    "                if dp[i-1][0] == -1:\n",
    "                    dp[i] = (1,dp[i-1][1]+1)\n",
    "                if dp[i-1][0] == 1 or dp[i-1][0] == 0:\n",
    "                    dp[i] = (1,2)\n",
    "                ans = max(ans,dp[i][1])\n",
    "            if arr[i] == arr[i-1]:\n",
    "                dp[i] = (0,0)\n",
    "            if arr[i] < arr[i-1]:\n",
    "                if dp[i-1][0] == 1:\n",
    "                    dp[i] = (-1,dp[i-1][1]+1)\n",
    "                if dp[i-1][0] == -1 or dp[i-1][0]==0:\n",
    "                    dp[i] = (-1,2)\n",
    "                ans = max(ans,dp[i][1])\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        # 长度为1直接返回\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        temp = [0 for _ in range(n-1)]\n",
    "        for i in range(1, n):\n",
    "            temp[i-1] = arr[i]-arr[i-1]\n",
    "        # 全部是同一个元素也直接返回1\n",
    "        x = 0\n",
    "        for num in temp:\n",
    "            if num != 0:\n",
    "                x += 1\n",
    "        if x == 0:\n",
    "            return 1\n",
    "        # 遍历一遍找异号\n",
    "        res, j, ans = 0 ,0 ,1\n",
    "        while j < n-2:\n",
    "            if temp[j]*temp[j+1]<0:\n",
    "                ans += 1\n",
    "            else:\n",
    "                res = max(res, ans)\n",
    "                ans = 1\n",
    "            j += 1\n",
    "        res = max(res, ans)\n",
    "        return res+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        inc = [1] * n # arr[i] > arr[i - 1]\n",
    "        dec = [1] * n # arr[i] < arr[i - 1]\n",
    "        for i in range(1, n):\n",
    "            if arr[i] > arr[i - 1]:\n",
    "                inc[i] = dec[i - 1] + 1\n",
    "                dec[i] = 1\n",
    "            elif arr[i] < arr[i - 1]:\n",
    "                dec[i] = inc[i - 1] + 1\n",
    "                inc[i] = 1\n",
    "            else:\n",
    "                inc[i] = 1\n",
    "                dec[i] = 1\n",
    "        return max(*inc, *dec)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, nums: List[int]) -> int:\n",
    "        # 动态规划\n",
    "        # 子问题定义：已nums[i]结尾的最长湍流子数组的长度\n",
    "        # 子问题联系：状态转移方程\n",
    "\n",
    "        # 存放长度\n",
    "        length = len(nums)\n",
    "        dp = [1 for _ in range(length)]\n",
    "\n",
    "        # 存放状态（0：小，1：大, 2：未知）\n",
    "        do = [2 for _ in range(length)]\n",
    "\n",
    "        # 连续子数组，O(n)时间复杂度\n",
    "        for i in range(1, length):\n",
    "            if do[i-1]==0:\n",
    "                if nums[i]>nums[i-1]:\n",
    "                    # 应该大\n",
    "                    dp[i] = dp[i-1]+1\n",
    "                    do[i] = 1\n",
    "                elif nums[i]==nums[i-1]:\n",
    "                    # 只有相等才可为2\n",
    "                    dp[i] = 1\n",
    "                    do[i] = 2\n",
    "                else:\n",
    "                    do[i] = 0\n",
    "                    dp[i] = 2\n",
    "            elif do[i-1]==1:\n",
    "                if nums[i]<nums[i-1]:\n",
    "                    # 应该小\n",
    "                    dp[i] = dp[i-1]+1\n",
    "                    do[i] = 0\n",
    "                elif nums[i]==nums[i-1]:\n",
    "                    # 只有相等才可为2\n",
    "                    dp[i] = 1\n",
    "                    do[i] = 2\n",
    "                else:\n",
    "                    dp[i] = 2\n",
    "                    do[i] = 1\n",
    "            else:\n",
    "                # 当前未知，则需要观察下一个元素\n",
    "                if nums[i]<nums[i-1]:\n",
    "                    dp[i] = dp[i-1]+1\n",
    "                    do[i] = 0\n",
    "                elif nums[i]>nums[i-1]:\n",
    "                    dp[i] = dp[i-1]+1\n",
    "                    do[i] = 1\n",
    "                else:\n",
    "                    # 继续未知\n",
    "                    dp[i] = 1\n",
    "                    do[i] = 2\n",
    "\n",
    "        # print('dp = ', dp)\n",
    "        # print('do = ', do)\n",
    "        return max(dp)\n",
    "\n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        ans = 1\n",
    "        f = [[1 for j in range(2)] for i in range(n)]\n",
    "        for i in range(1, n):\n",
    "            if arr[i] == arr[i - 1]:\n",
    "                f[i][0] = 1\n",
    "                f[i][1] = 1\n",
    "            elif arr[i] > arr[i - 1]:\n",
    "                f[i][0] = 1\n",
    "                f[i][1] = f[i - 1][0] + 1\n",
    "            else:  # arr[i] < arr[i - 1]\n",
    "                f[i][0] = f[i - 1][1] + 1\n",
    "                f[i][1] = 1\n",
    "            ans = max(ans, f[i][0], f[i][1])\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        up, down = [1 for _ in range(len(arr))], [1 for _ in range(len(arr))]\n",
    "        res = 1\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i] > arr[i - 1]:\n",
    "                up[i] = down[i - 1] + 1\n",
    "            elif arr[i] < arr[i - 1]:\n",
    "                down[i] = up[i - 1] + 1\n",
    "            res = max(res, up[i], down[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        l = r = 1\n",
    "        res = 2 if len(set(arr))!=1 else 1 \n",
    "        while r+1<len(arr):\n",
    "            if arr[r-1]<arr[r]>arr[r+1] or arr[r-1]>arr[r]<arr[r+1]:\n",
    "                res = max(res,r-l+3)\n",
    "            else:\n",
    "                l=r+1\n",
    "            r+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        def turbulent(a, b, c):\n",
    "            return (a < b and b > c) or (a > b and b < c)\n",
    "\n",
    "        if len(arr) == 1:\n",
    "            return 1\n",
    "\n",
    "        dp = [i + 1 for i, _ in enumerate(arr)]\n",
    "        dp[1] = 1 if arr[1] == arr[0] else 2\n",
    "        for i in range(2, len(arr)):\n",
    "            if turbulent(arr[i - 2], arr[i - 1], arr[i]):\n",
    "                dp[i] = dp[i - 1] + 1\n",
    "            else:\n",
    "                dp[i] = 1 if arr[i] == arr[i - 1] else 2\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[1, 1] for _ in range(n)]\n",
    "        ret = 1\n",
    "        for i in range(1, n):\n",
    "            if arr[i] < arr[i-1]:\n",
    "                dp[i][1] = dp[i-1][0] + 1\n",
    "                ret = max(ret, dp[i][1])\n",
    "            elif arr[i] > arr[i-1]:\n",
    "                dp[i][0] = dp[i-1][1] + 1\n",
    "                ret = max(ret, dp[i][0])\n",
    "\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "    def maxTurbulenceSize(self,arr):\n",
    "        dp = [[1, 1] for _ in range(len(arr))]\n",
    "        dp[0][0] = dp[0][1] = 1\n",
    "\n",
    "        for i in range(1, len(arr)):\n",
    "            if (arr[i - 1] > arr[i]):\n",
    "                dp[i][0] = dp[i - 1][1] + 1\n",
    "            elif (arr[i - 1] < arr[i]):\n",
    "                dp[i][1] = dp[i - 1][0] + 1\n",
    "\n",
    "        res = 1\n",
    "        for i in range(len(arr)):\n",
    "            res = max(res, dp[i][0], dp[i][1])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        # dp[i]=[up, down]:记录以i元素结尾的上升及下降湍流子数组长度\n",
    "        # i > i-1: dp[i][0]=dp[i-1][1]+1\n",
    "        # i < i-1: dp[i][1]=dp[i-1][0]+1\n",
    "        n = len(arr)\n",
    "        dp = [[1, 1] for _ in range(n)]\n",
    "        res = 1\n",
    "        for i in range(1, n):\n",
    "            if arr[i] > arr[i-1]:\n",
    "                dp[i][0] = dp[i-1][1] + 1\n",
    "            if arr[i] < arr[i-1]:\n",
    "                dp[i][1] = dp[i-1][0] + 1\n",
    "            res = max(res, max(dp[i]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "    def maxTurbulenceSize(self,arr):\n",
    "        dp = [[1, 1] for _ in range(len(arr))]\n",
    "        dp[0][0] = dp[0][1] = 1\n",
    "\n",
    "        for i in range(1, len(arr)):\n",
    "            if (arr[i - 1] > arr[i]):\n",
    "                dp[i][0] = dp[i - 1][1] + 1\n",
    "            elif (arr[i - 1] < arr[i]):\n",
    "                dp[i][1] = dp[i - 1][0] + 1\n",
    "\n",
    "        res = 1\n",
    "        for i in range(len(arr)):\n",
    "            res = max(res, dp[i][0], dp[i][1])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        if len(set(arr))==1:\n",
    "            return 1\n",
    "        if len(arr)==2:\n",
    "            return 2\n",
    "        i=0\n",
    "        j=1\n",
    "        res = 1\n",
    "\n",
    "        while j<(len(arr)-1):\n",
    "            print(i,j)\n",
    "            if not ((arr[j]<arr[j-1] and arr[j]<arr[j+1]) or (arr[j]>arr[j-1] and arr[j]>arr[j+1])):\n",
    "                i=j\n",
    "            j+=1\n",
    "            res = max(res,j-i+1)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        # dp[i]=[up, down]:记录以i元素结尾的上升及下降湍流子数组长度\n",
    "        # i > i-1: dp[i][0]=dp[i-1][1]+1\n",
    "        # i < i-1: dp[i][1]=dp[i-1][0]+1\n",
    "        n = len(arr)\n",
    "        dp = [[1, 1] for _ in range(n)]\n",
    "        res = 1\n",
    "        for i in range(1, n):\n",
    "            if arr[i] > arr[i-1]:\n",
    "                dp[i][0] = dp[i-1][1] + 1\n",
    "            if arr[i] < arr[i-1]:\n",
    "                dp[i][1] = dp[i-1][0] + 1\n",
    "            res = max(res, max(dp[i]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        f = [[1, 1] for _ in range(n)]\n",
    "        # f[0] = [1, 1]\n",
    "        ans = 1\n",
    "        for i in range(1, n):\n",
    "            if arr[i] > arr[i-1]:\n",
    "                f[i][0] = f[i-1][1] + 1\n",
    "            elif arr[i] < arr[i-1]:\n",
    "                f[i][1] = f[i-1][0] + 1\n",
    "            ans = max(ans, max(f[i]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "\n",
    "        n = len(arr)\n",
    "        f = [[1, 1] for _ in range(n)]\n",
    "\n",
    "\n",
    "        res = 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if arr[i] > arr[i-1]:\n",
    "                f[i][0] = f[i-1][1] + 1 \n",
    "            elif arr[i] < arr[i-1]:\n",
    "                f[i][1] = f[i-1][0] + 1 \n",
    "            res = max(f[i][0], f[i][1], res)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        error = [arr[i] - arr[i+1] for i in range(n-1)] # len = n-1\n",
    "        if n==1 or max([abs(x) for x in error]) == 0:\n",
    "            return 1\n",
    "        elif n == 2:\n",
    "            return 2\n",
    "        print(f'error:{error}')\n",
    "        pre, post, ans = 0, 1, 1\n",
    "        while post < n-1:\n",
    "            tmp_len = 1\n",
    "            while True:\n",
    "                if post >= n-1:\n",
    "                    break\n",
    "                if error[post] * error[post-1] < 0:\n",
    "                    tmp_len += 1\n",
    "                    post += 1\n",
    "                elif error[post] * error[post-1] > 0:\n",
    "                    pre = post\n",
    "                    post = pre + 1\n",
    "                    break\n",
    "                elif error[post] == 0:\n",
    "                    pre = post + 1\n",
    "                    post = pre + 1\n",
    "                    break\n",
    "                else:\n",
    "                    while error[pre] == 0:\n",
    "                        pre += 1\n",
    "                    post = pre + 1\n",
    "                    break\n",
    "            ans = max(ans, tmp_len+1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "\n",
    "        # n = len(arr)\n",
    "\n",
    "        # dp = [[1]*2 for _ in range(n)]\n",
    "\n",
    "        # for i in range(1, n):\n",
    "        #     if arr[i] > arr[i-1]:\n",
    "        #         dp[i][1] = 1 + dp[i-1][0]\n",
    "        #     elif arr[i] < arr[i-1]:\n",
    "        #         dp[i][0] = 1 + dp[i-1][1]\n",
    "        \n",
    "        # big, less = 0, 0\n",
    "        # for i in range(n):\n",
    "        #     big = max(big, dp[i][1])\n",
    "        #     less = max(less, dp[i][0])\n",
    "        # return big if big > less else less\n",
    "\n",
    "\n",
    "        n = len(arr)\n",
    "\n",
    "        dp = [[1]*2 for _ in range(n)]\n",
    "        dp_0, dp_1 = 1, 1\n",
    "        big = 1\n",
    "        for i in range(1, n):\n",
    "            if arr[i] > arr[i-1]:\n",
    "                dp_1 = 1 + dp_0\n",
    "                dp_0 = 1\n",
    "                big = max(big, dp_1)\n",
    "            elif arr[i] < arr[i-1]:\n",
    "                dp_0 = 1 + dp_1\n",
    "                dp_1 = 1\n",
    "                big = max(big, dp_0)\n",
    "            else:\n",
    "                dp_0, dp_1 = 1, 1\n",
    "        \n",
    "  \n",
    "        return big\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        # dp[i]=[up, down]:记录以i元素结尾的上升及下降湍流子数组长度\n",
    "        # i > i-1: dp[i][0]=dp[i-1][1]+1\n",
    "        # i < i-1: dp[i][1]=dp[i-1][0]+1\n",
    "        n = len(arr)\n",
    "        dp = [[1]*2 for _ in range(n)]\n",
    "        res = 1\n",
    "        for i in range(1, n):\n",
    "            if arr[i] > arr[i-1]:\n",
    "                dp[i][0] = dp[i-1][1] + 1\n",
    "            if arr[i] < arr[i-1]:\n",
    "                dp[i][1] = dp[i-1][0] + 1\n",
    "            res = max(res, max(dp[i]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "\n",
    "        dp = [[0 for _ in range(2)] for _ in range(len(arr))]\n",
    "        \n",
    "        dp[0][0],dp[0][1] = 1,1\n",
    "\n",
    "        ans = 1\n",
    "        for i in range(1,len(arr)):\n",
    "            if arr[i]==arr[i-1]:\n",
    "                dp[i][0],dp[i][1] = 1,1\n",
    "            elif arr[i]>arr[i-1]:\n",
    "                dp[i][0] = 1\n",
    "                dp[i][1] = dp[i-1][0]+1\n",
    "            else:\n",
    "                dp[i][0] = dp[i-1][1]+1\n",
    "                dp[i][1] = 1\n",
    "            ans = max(ans,dp[i][0],dp[i][1])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        if len(set(arr)) == 1:\n",
    "            return 1\n",
    "        res = []\n",
    "        for i in range(n-1):\n",
    "            if arr[i] > arr[i+1]:\n",
    "                res.append(1)\n",
    "            elif arr[i] == arr[i+1]:\n",
    "                res.append(0)\n",
    "            else:\n",
    "                res.append(-1)\n",
    "        print(res)\n",
    "        if len(res) == 1:\n",
    "            return 2\n",
    "        count = 1\n",
    "        mx = 0\n",
    "        for i in range(0, len(res)-1):\n",
    "\n",
    "            if res[i] * res[i+1] == -1:\n",
    "                count += 1\n",
    "                mx = max(count,mx)\n",
    "            else: \n",
    "                mx = max(count, mx)\n",
    "                count  = 1\n",
    "                continue\n",
    "        return mx+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        if len(set(arr)) == 1:\n",
    "            return 1\n",
    "        if len(arr) == 1:\n",
    "            return 1\n",
    "        elif len(arr) == 2:\n",
    "            return 2\n",
    "\n",
    "        def compareResults(num1,num2):\n",
    "            if num1 > num2:\n",
    "                return 1\n",
    "            elif num1 < num2:\n",
    "                return 2\n",
    "            else:\n",
    "                return 3\n",
    "        longest = 0\n",
    "        counter = 0\n",
    "        #len>2\n",
    "        last = compareResults(arr[0], arr[1])\n",
    "        for i in range(1,len(arr) -1):\n",
    "            \n",
    "            current_result =compareResults(arr[i], arr[i+1])\n",
    "           # print(\"last,current_result=\",last,current_result)\n",
    "            #print(\"counter=\", counter)\n",
    "            if (last == 1 and current_result == 2) or (last == 2 and current_result == 1):\n",
    "                if counter == 0:\n",
    "                    counter =3\n",
    "                else:\n",
    "                    counter += 1\n",
    "                #最后一次需要计数\n",
    "                if i == len(arr) -2:\n",
    "                    longest = max(longest,counter)\n",
    "            else:#除了变化，其他情况,才开始计数\n",
    "                longest = max(longest,counter)\n",
    "                counter = 0\n",
    "            last = current_result\n",
    "        \n",
    "        return longest if longest != 0 else 2\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        4,8,12,16\n",
    "        4, 4 4\n",
    "        16, 16\n",
    "        \"\"\"\n",
    "        if len(arr) <= 1:\n",
    "            return len(arr)\n",
    "        if len(arr) == 2:\n",
    "            if arr[0] == arr[1]:\n",
    "                return 1\n",
    "            else:\n",
    "                return 2\n",
    "        minus_list = []\n",
    "        for i in range(1, len(arr)):\n",
    "            minus_list.append(arr[i] - arr[i-1])\n",
    "        times_list = []\n",
    "        for i in range(1, len(minus_list)):\n",
    "            times_list.append(minus_list[i] * minus_list[i-1])\n",
    "        result = 0\n",
    "        now_times = 0\n",
    "        all_zero = True\n",
    "        for v in minus_list:\n",
    "            if v != 0:\n",
    "                all_zero = False\n",
    "        for v in times_list:\n",
    "            if v < 0:\n",
    "                now_times += 1\n",
    "            else:\n",
    "                result = max(result, now_times)\n",
    "                now_times = 0\n",
    "        result = max(result, now_times)\n",
    "        if result != 0:\n",
    "            return result + 2\n",
    "        else:\n",
    "            if all_zero:\n",
    "                return 1\n",
    "            else:\n",
    "                return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "\n",
    "        n = len(arr)\n",
    "\n",
    "        dp = [[1]* 2 for _ in range(n)]\n",
    "        #print(dp)\n",
    "        ans = 0\n",
    "        for i in range(1,n):\n",
    "            if arr[i-1] > arr[i]:\n",
    "                dp[i][0] = dp[i-1][1] +1\n",
    "            elif arr[i-1] < arr[i]:\n",
    "                dp[i][1] = dp[i-1][0] +1\n",
    "        for i in range(n):\n",
    "            ans = max(ans,dp[i][0])\n",
    "            ans = max(ans,dp[i][1])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        inc = [1] * n # arr[i] > arr[i - 1]\n",
    "        dec = [1] * n # arr[i] < arr[i - 1]\n",
    "        for i in range(1, n):\n",
    "            if arr[i] > arr[i - 1]:\n",
    "                inc[i] = dec[i - 1] + 1\n",
    "                dec[i] = 1\n",
    "            elif arr[i] < arr[i - 1]:\n",
    "                dec[i] = inc[i - 1] + 1\n",
    "                inc[i] = 1\n",
    "            else:\n",
    "                inc[i] = 1\n",
    "                dec[i] = 1\n",
    "        return max(*inc, *dec)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        if len(set(arr)) == 1:\n",
    "            return 1\n",
    "        if len(arr) == 1:\n",
    "            return 1\n",
    "        elif len(arr) == 2:\n",
    "            return 2\n",
    "\n",
    "        def compareResults(num1,num2):\n",
    "            if num1 > num2:\n",
    "                return 1\n",
    "            elif num1 < num2:\n",
    "                return 2\n",
    "            else:\n",
    "                return 3\n",
    "        longest = 0\n",
    "        counter = 0\n",
    "        #len>2\n",
    "        last = compareResults(arr[0], arr[1])\n",
    "        for i in range(1,len(arr) -1):\n",
    "            \n",
    "            current_result =compareResults(arr[i], arr[i+1])\n",
    "           # print(\"last,current_result=\",last,current_result)\n",
    "            #print(\"counter=\", counter)\n",
    "            if (last == 1 and current_result == 2) or (last == 2 and current_result == 1):\n",
    "                if counter == 0:\n",
    "                    counter =3\n",
    "                else:\n",
    "                    counter += 1\n",
    "                #最后一次需要计数\n",
    "                if i == len(arr) -2:\n",
    "                    longest = max(longest,counter)\n",
    "            else:#除了变化，其他情况,才开始计数\n",
    "                longest = max(longest,counter)\n",
    "                counter = 0\n",
    "            last = current_result\n",
    "        \n",
    "        return longest if longest != 0 else 2\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, A: List[int]) -> int:\n",
    "        n = len(A)\n",
    "        f = [[1, 1] for _ in range(n)]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if A[i - 1] > A[i]:\n",
    "                f[i][0] = f[i - 1][1] + 1\n",
    "            elif A[i - 1] < A[i]:\n",
    "                f[i][1] = f[i - 1][0] + 1\n",
    "\n",
    "        max_size = 1\n",
    "        for i in range(n):\n",
    "            max_size = max(max_size, f[i][0])\n",
    "            max_size = max(max_size, f[i][1])\n",
    "\n",
    "        return max_size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        if len(set(arr)) == 1:\n",
    "            return 1\n",
    "        if len(arr) == 2:\n",
    "            return 2\n",
    "        #逆序遍历使得arr[i] = arr[i] - arr[i-1],\n",
    "        for i in range(len(arr)-1,0,-1):\n",
    "            arr[i] = arr[i]-arr[i-1]\n",
    "        arr = arr[1:]\n",
    "\n",
    "        res = []\n",
    "        count = 0\n",
    "        for i in range(len(arr)-1):\n",
    "            if arr[i] * arr[i+1] < 0:\n",
    "                count += 1\n",
    "            else:\n",
    "                res.append(count)\n",
    "                count = 0\n",
    "        res.append(count)\n",
    "        return max(res) + 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        '''\n",
    "        [9,4,2,10,7,8,8,1,9]\n",
    "          \n",
    "        '''\n",
    "        N=len(arr)\n",
    "        if len(set(arr))==1:\n",
    "            return 1\n",
    "        if len(arr)==2:\n",
    "            return 2\n",
    "        temp=[]\n",
    "        for i in range(1,N):\n",
    "            temp.append(arr[i]-arr[i-1])\n",
    "        print(temp)\n",
    "        i=0\n",
    "        j=i\n",
    "        k=j+1\n",
    "        ans=0\n",
    "        while k<len(temp):\n",
    "            if temp[k]*temp[j]>=0:\n",
    "\n",
    "                ans=max(ans,j-i+1)\n",
    "                i=k\n",
    "                j=i\n",
    "                k=j+1\n",
    "            else:\n",
    "\n",
    "                ans=max(ans,k-i+1)\n",
    "                j+=1\n",
    "                k+=1\n",
    "                print(i,k,ans)\n",
    "                \n",
    "                \n",
    "        return ans+1  \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def maxTurbulenceSize(arr):  \n",
    "    n = len(arr)  \n",
    "    dp = [[1, 1] for _ in range(n)]  \n",
    "      \n",
    "    for i in range(1, n):  \n",
    "        if arr[i-1] > arr[i]:  \n",
    "            dp[i][0] = dp[i-1][1] + 1  \n",
    "        elif arr[i-1] < arr[i]:  \n",
    "            dp[i][1] = dp[i-1][0] + 1  \n",
    "      \n",
    "    ret = max(dp[i][0] for i in range(n))  \n",
    "    ret = max(ret, max(dp[i][1] for i in range(n)))  \n",
    "    return ret\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        return maxTurbulenceSize(arr)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        # if n <= 2:\n",
    "        #     return n \n",
    "        dp = [[1,1] for _ in range(n)]\n",
    "        max_len = 1\n",
    "        dp[0] = [1,1]\n",
    "        for i in range(1, n):\n",
    "            if arr[i] > arr[i-1]:\n",
    "                dp[i][1] = dp[i-1][0] + 1\n",
    "            elif arr[i] < arr[i-1]:\n",
    "                dp[i][0] = dp[i-1][1] + 1\n",
    "            max_len = max(max_len, dp[i][0], dp[i][1])\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[1,1] for _ in range(n)]\n",
    "        result = 1\n",
    "        for i in range(1,n):\n",
    "            if(arr[i] > arr[i-1]):\n",
    "                dp[i][0] = 1\n",
    "                dp[i][1] = dp[i-1][0] + 1\n",
    "            elif(arr[i] < arr[i-1]):\n",
    "                dp[i][0] = dp[i-1][1] + 1\n",
    "                dp[i][1] = 1\n",
    "            else:\n",
    "                dp[i][0] = 1\n",
    "                dp[i][1] = 1\n",
    "            result = max(result, dp[i][0], dp[i][1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[1, 1] for _ in range(n)]\n",
    "        \n",
    "        # 0 down 1 up\n",
    "        for i in range(1, n):\n",
    "            if arr[i] > arr[i-1]:\n",
    "                dp[i][1] = dp[i-1][0] + 1\n",
    "            elif arr[i] < arr[i-1]:\n",
    "                dp[i][0] = dp[i-1][1] + 1\n",
    "        \n",
    "        rst = 0\n",
    "        for i in range(n):\n",
    "            rst = max(rst, dp[i][0], dp[i][1])\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        m = len(arr)\n",
    "        dp = [[0, 0] for _ in range(m)]\n",
    "        dp[0][0] = dp[0][1] = 1\n",
    "        if len(arr)>1:\n",
    "            dp[1][0] = 2 if arr[0]>arr[1] else 1\n",
    "            dp[1][1] = 2 if arr[0]<arr[1] else 1\n",
    "        for i in range(2, m):\n",
    "            if arr[i-1]>arr[i]:\n",
    "                dp[i][0] = dp[i-1][1]+1\n",
    "                dp[i][1] = 1\n",
    "            elif arr[i-1]<arr[i]:\n",
    "                dp[i][1] = dp[i-1][0]+1\n",
    "                dp[i][0] = 1\n",
    "            else:\n",
    "                dp[i][0] = dp[i][1] = 1\n",
    "        return max(max(a) for a in dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[1,1] for _ in range(n)]\n",
    "        result = 1\n",
    "        for i in range(1,n):\n",
    "            if(arr[i] > arr[i-1]):\n",
    "                dp[i][1] = dp[i-1][0] + 1\n",
    "            elif(arr[i] < arr[i-1]):\n",
    "                dp[i][0] = dp[i-1][1] + 1\n",
    "            result = max(result, dp[i][0], dp[i][1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        ans,j,n=0,0,len(arr)\n",
    "        if len(set(arr))==1:\n",
    "            return 1\n",
    "        temp=arr[1]-arr[0]\n",
    "        if n==2:\n",
    "            return 2\n",
    "        for i in range(2,n):\n",
    "            if (arr[i]-arr[i-1])*temp<0:\n",
    "                temp=arr[i]-arr[i-1]\n",
    "                ans=max(ans,i-j+1)\n",
    "            else:\n",
    "                temp=arr[i]-arr[i-1]\n",
    "                ans=max(i-j,ans)\n",
    "                j=i-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        dp = [[1,1] for _ in range(n)] \n",
    "\n",
    "        for i in range(1, n):\n",
    "            if arr[i] > arr[i-1]:\n",
    "                dp[i][1] =dp[i-1][0] + 1\n",
    "            elif arr[i] < arr[i-1]:\n",
    "                dp[i][0] =dp[i-1][1] + 1\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res = max(res, max( dp[i][0],  dp[i][1]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        dp = [[1, 1]]\n",
    "        ans = 1\n",
    "        for index in range(1, len(arr)):\n",
    "            tmp = [1, 1]\n",
    "            if arr[index] < arr[index - 1]:\n",
    "                tmp[0] += dp[-1][1]\n",
    "            elif arr[index] > arr[index - 1]:\n",
    "                tmp[1] += dp[-1][0]\n",
    "            ans = max(ans, max(tmp))\n",
    "            dp.append(tmp.copy())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTurbulenceSize(self, arr: List[int]) -> int:\n",
    "        ans,j,n=0,0,len(arr)\n",
    "        if len(set(arr))==1:\n",
    "            return 1\n",
    "        temp=arr[1]-arr[0]\n",
    "        if n==2:\n",
    "            return 2\n",
    "        for i in range(2,n):\n",
    "            if (arr[i]-arr[i-1])*temp<0:\n",
    "                temp=arr[i]-arr[i-1]\n",
    "                ans=max(ans,i-j+1)\n",
    "                continue\n",
    "            else:\n",
    "                temp=arr[i]-arr[i-1]\n",
    "                ans=max(i-j,ans)\n",
    "                j=i-1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
